package com.javaweb.util.test;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;
import java.util.regex.Pattern;

import com.javaweb.constant.CommonConstant;
import com.javaweb.util.help.tree.BinaryTree;

/**
 * 【人类更易理解】中缀表达式（日常认知的表达式）：(3+4)*5-6
 * 【计算机更易理解】前缀表达式（波兰式）：-*+3456
 * 【计算机易理解】后缀表达式（逆波兰式）：34+5*6-
 */
public class ExpressionHandle {
	
	//数字正则（0123456789）
	public static final Pattern DIGIT_PATTERN = Pattern.compile("[0-9]");
	//运算符正则（+-*/）
	public static final Pattern OPERATOR_PATTERN = Pattern.compile("[+-\\\\*\\\\/]");
	//左括号
	public static final String LEFT_BRACKET = "(";
	//右括号
	public static final String RIGHT_BRACKET = ")";
	
	//定义操作符优先级
	public static final Map<String,Integer> OPERATOR_LEVEL = new HashMap<>(); 
	static{
		OPERATOR_LEVEL.put("+",1);//加
		OPERATOR_LEVEL.put("-",1);//减
		OPERATOR_LEVEL.put("*",2);//乘
		OPERATOR_LEVEL.put("/",2);//除
		OPERATOR_LEVEL.put(LEFT_BRACKET,3);//左括号
		OPERATOR_LEVEL.put(RIGHT_BRACKET,3);//右括号
	};
	
	/**
	 * 将中缀表达式转为后缀表达式（逆波兰式）
 	 * <p>
 	 * 规则1：非操作符（即数字）不用进栈，直接入集合
 	 * <p>
 	 * 规则2：栈为空或遇到操作符为左括号，直接将操作符入栈；遇到操作符为右括号，将栈内左右括号的内容全部入集合
 	 * <p>
 	 * 规则3：栈顶为左括号，直接将操作符入栈
 	 * <p>
 	 * 规则4：操作符优先级比栈顶操作符优先级高，直接将操作符入栈；反之，将栈顶出栈入集合，并继续比较规则1到4
	 * @param str 分割表达式字符数组
	 * @return 后缀表达式集合
	 */
	public static List<String> infixExpression2PostfixExpression(String expression){
		List<String> peList = new ArrayList<String>();
		Stack<String> stack = new Stack<String>();
		for(int i=0;i<expression.length();i++){
			String each = String.valueOf(expression.charAt(i));
			if(!each.trim().equals(CommonConstant.EMPTY_VALUE)) {
				if(OPERATOR_LEVEL.get(each)!=null) {//操作符
					if(stack.empty()) {//栈为空直接入栈
						stack.add(each);
						continue;
					}
					if(Objects.equals(LEFT_BRACKET,each)) {//操作符为左括号，直接入栈
						stack.add(each);
						continue;
					}
					if((Objects.equals(RIGHT_BRACKET,each))&&(stack.contains(LEFT_BRACKET))) {//操作符为右括号且栈中有左括号，弹出栈中括号内所有元素（包括括号）入集合
						stack.add(each);
						while(true) {
							String pop = stack.pop();
							if((!Objects.equals(LEFT_BRACKET,pop))&&(!Objects.equals(RIGHT_BRACKET,pop))){
								peList.add(pop);
							}
							if(Objects.equals(LEFT_BRACKET,pop)) {
								break;
							}
						}
						continue;
					}
					String lastElement = stack.lastElement();
					if(Objects.equals(LEFT_BRACKET,lastElement)) {//栈顶为左括号，直接将操作符入栈
						stack.add(each);
						continue;
					}
					if(hasHigherPrecedence(each/*操作符*/,lastElement/*栈顶元素*/)) {//操作符优先级比栈顶操作符优先级高，直接入栈
						stack.add(each);
					}else{//操作符优先级比栈顶操作符优先级低或相等，弹出栈顶操作符入集合，并继续比较
						peList.add(stack.pop());
						i--;
					}
				}else {//非操作符
					peList.add(each);
				}
			}
		}
		while(!stack.isEmpty()) {//最后还有剩余则出栈
			peList.add(stack.pop());
		}
		return peList;
	}
	
	//构建二叉树
	public static BinaryTree<String> buildBinaryTree(List<String> expressionList) {
		Stack<BinaryTree<String>> stack = new Stack<>();  
		for(String str:expressionList) {
			if(DIGIT_PATTERN.matcher(str).matches()) {//数字
				stack.push(new BinaryTree<String>(str));
			} else if(OPERATOR_PATTERN.matcher(str).matches()) {//运算符
				BinaryTree<String> leftNode = stack.pop();//注意顺序
				BinaryTree<String> rightNode = stack.pop();//注意顺序
				BinaryTree<String> currentNode = new BinaryTree<>(str);
				currentNode.setLeftNode(rightNode);//注意顺序
				currentNode.setRightNode(leftNode);//注意顺序
				stack.push(currentNode);
			}
		}
		return stack.pop();
	}
	
	//计算二叉树
	public static BigDecimal calBinaryTree(BinaryTree<String> binaryTreeRoot) {
		String value = binaryTreeRoot.getValue();
		if(DIGIT_PATTERN.matcher(value).matches()) {
			return new BigDecimal(value);
		} else {
			BigDecimal leftNode = calBinaryTree(binaryTreeRoot.getLeftNode());
			BigDecimal rightNode = calBinaryTree(binaryTreeRoot.getRightNode());
			return switch(value) {
				case "+" -> leftNode.add(rightNode);
				case "-" -> leftNode.subtract(rightNode);
				case "*" -> leftNode.multiply(rightNode);
				case "/" -> leftNode.divide(rightNode,2,RoundingMode.HALF_UP);
				default -> throw new IllegalArgumentException("Unexpected value: " + value);
			};
		}
	}
	
	//检查操作符的优先级是否更高
	public static boolean hasHigherPrecedence(String c1,String c2) {  
        return OPERATOR_LEVEL.get(c1) > OPERATOR_LEVEL.get(c2);  
    }

	public static void main(String[] args) throws Exception {
		//String expression = "(3+4)*5-6";//前缀表达式
		String expression = "(3+7)*5-(2*6+1)";//前缀表达式
		List<String> list = infixExpression2PostfixExpression(expression);
		System.out.println(list);
		BinaryTree<String> binaryTree = buildBinaryTree(list);
		System.out.println(calBinaryTree(binaryTree));
	}

}
